package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/*
113. 路径总和II
 */
public class Of20210313LeetCode113 {
    /*
    给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
     */
    public static void main(String[] args) {
        TreeNode node = new TreeNode(5, new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))
                , null), new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))));
        System.out.println(pathSum(node, 22));
    }

    private static List<List<Integer>> result = new ArrayList<>();
    private static List<Integer> path = new ArrayList<>();

    private static void traversal(TreeNode cur, int count) {
        if (cur.left == null && cur.right == null) {
            if (count == 0){
                List<Integer> list = new ArrayList<>(path);// 遇到了叶子节点切找到了和为sum的路径
                result.add(list);
            }

            return;// 遇到叶子节点而没有找到合适的边，直接返回
        }
        if (cur.left != null) {
            path.add(cur.left.val);
            traversal(cur.left, count - cur.left.val);// 递归
            path.remove(path.size() - 1);// 回溯
        }
        if (cur.right != null) {
            path.add(cur.right.val);
            traversal(cur.right, count - cur.right.val);// 递归
            path.remove(path.size() - 1);// 回溯
        }
        return;
    }

    private static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) return result;
        path.add(root.val);
        traversal(root, targetSum - root.val);
        return result;
    }
}
